package com.example.arithmeticleetcode.leetcode.jan;

import java.util.*;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2021-01-06 13:16
 **/
public class Demo04 {

    public static void main(String[] args) {
        List<List<String>> equations = new ArrayList<>();
        List<String> a = Arrays.asList("a", "b");
        List<String> b = Arrays.asList("b", "c");
        List<String> c = Arrays.asList("bc", "cd");
        equations.add(a);
        equations.add(b);
        equations.add(c);
        double[] values = {1.5,2.5,5.0};
        List<List<String>> queries = new ArrayList<>();
        List<String> a1 = Arrays.asList("b", "cd");
        List<String> b1 = Arrays.asList("c", "b");
        List<String> c1 = Arrays.asList("bc", "cd");
        List<String> d1 = Arrays.asList("cd", "bc");
        queries.add(a1);
        queries.add(b1);
        queries.add(c1);
        queries.add(d1);

        new Demo04().calcEquation2(equations, values, queries);
    }



    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        //判断是否包含
        Map<String, Map<String, Double>> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        Map<String, Double> littleMap = null;
        for (int i = 0, len = equations.size(); i < len; i++) {
            List<String> list = equations.get(i);
            set.add(list.get(0));
            set.add(list.get(1));
            littleMap = new HashMap<>();
            littleMap.put(list.get(1), values[i]);
            map.put(list.get(0), littleMap);
        }
        double[] ret = new double[queries.size()];
        for (int i = 0, len = queries.size(); i < len; i++) {
            List<String> list = queries.get(i);
            String s1 = list.get(0);
            String s2 = list.get(1);
            if (set.contains(s1) && set.contains(s2)) {
                if (s1.equals(s2)) {
                    ret[i] = 1.0;
                    continue;
                }
                Map<String, Double> map1 = map.get(s1);
                if (map1 != null) {
                    if (map.containsKey(s2)) {
                        ret[i] = map.get(s1).get(s2);
                    } else {
                        ret[i] = getValue(s2, 1.0, map, map1);
                    }
                    continue;
                }
                Map<String, Double> map2 = map.get(s2);
                if (map2 != null) {
                    if (map.containsKey(s1)) {
                        ret[i] = 1 / map.get(s1).get(s2);
                    } else {
                        ret[i] = 1 / getValue(s1, 1.0, map, map2);
                    }
                }
            } else {
                ret[i] = -1.0;
            }
        }
        return ret;
    }

    private double getValue(String s2, double value, Map<String, Map<String, Double>> map, Map<String, Double> map1) {
        for (Map.Entry<String, Double> entry : map1.entrySet()) {
            String key = entry.getKey();
            if (map.get(key) == null) {
                return -1.0;
            } else {
                value *= entry.getValue();
                if (s2.equals(entry)) {
                    return value;
                }
                getValue(s2, value, map, map.get(key));
            }
        }
        return value;
    }



    public double[] calcEquation2(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int equationSize = equations.size();
        UnionFind unionFind = new UnionFind(equationSize << 1);
        Map<String, Integer> map = new HashMap<>(equationSize << 1);
        int id = 0;
        for (int i = 0; i < equationSize; i++) {
            List<String> equation = equations.get(i);
            String var1 = equation.get(0);
            String var2 = equation.get(1);
            if (!map.containsKey(var1)) {
                map.put(var1, id);
                id++;
            }
            if (!map.containsKey(var2)) {
                map.put(var2, id);
                id++;
            }
            unionFind.union(map.get(var1), map.get(var2), values[i]);
        }

        int queriesSize = queries.size();
        double[] ret = new double[queriesSize];
        for (int i = 0; i < queriesSize; i++) {
            String var1 = queries.get(i).get(0);
            String var2 = queries.get(i).get(1);
            Integer id1 = map.get(var1);
            Integer id2 = map.get(var2);
            if (id1 == null || id2 == null) {
                ret[i] = -1.0;
            } else {
                ret[i] = unionFind.isConnected(id1, id2);
            }
        }
        return ret;

    }

    private class UnionFind{
        private int[] parent;

        private double[] weight;

        public UnionFind(int n) {
            this.parent = new int[n];
            this.weight = new double[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                weight[i] = 1.0;
            }
        }

        public void union(int x, int y, double value) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            parent[rootX] = rootY;
            weight[rootX] = weight[y] * value / weight[x];

        }

        public int find(int x) {
            if (x != parent[x]) {
                int origin = parent[x];
                parent[x] = find(parent[x]);
                weight[x] *= weight[origin];
            }
            return parent[x];
        }

        public double isConnected(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return weight[x] / weight[y];
            } else {
                return -1.0;
            }
        }


    }

}
